{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# **实验十一 图的遍历操作**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- # %%html -->\n",
    "<img src=\"实验十.png\" width=\"70%\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'b', 'c', 'd', 'e']\n"
     ]
    }
   ],
   "source": [
    "class Graph(object):\n",
    "    def __init__(self, graph_dict=None):\n",
    "        if graph_dict is None:\n",
    "            graph_dict = {}\n",
    "        self.graph_dict = graph_dict\n",
    "\n",
    "    def getVertices(self):\n",
    "        '''\n",
    "        得到图的所有顶点\n",
    "        '''\n",
    "        return list(self.graph_dict.keys())\n",
    "\n",
    "    def addVertex(self, vertex):\n",
    "        '''\n",
    "        添加一个顶点\n",
    "        '''\n",
    "        if vertex not in self.graph_dict:\n",
    "            self.graph_dict[vertex] = {}\n",
    "\n",
    "    def addEdge(self, edge):\n",
    "        '''\n",
    "        添加一个边\n",
    "        '''\n",
    "        edge = set(edge)\n",
    "        (vertex1, vertex2) = tuple(edge)\n",
    "        if vertex1 in self.graph_dict:\n",
    "            self.graph_dict[vertex1].add(vertex2)\n",
    "        else:\n",
    "            self.graph_dict[vertex1] = {vertex2, }\n",
    "\n",
    "    def findEdge(self):\n",
    "        '''\n",
    "        打印所有的边\n",
    "        '''\n",
    "        edgename = []\n",
    "        for vertex in self.graph_dict:\n",
    "            for nxtvertex in self.graph_dict[vertex]:\n",
    "                if {nxtvertex, vertex} not in edgename:\n",
    "                    edgename.append({vertex, nxtvertex})\n",
    "        return edgename\n",
    "\n",
    "    def dfs(self, node, visited=None):\n",
    "        '''\n",
    "        深度优先遍历\n",
    "        :param node:\n",
    "        :param visited:\n",
    "        :return:\n",
    "        '''\n",
    "        if visited is None:\n",
    "            visited = set()\n",
    "        visited.add(node)\n",
    "        print(node)\n",
    "        for next in self.graph_dict[node] - visited:\n",
    "            self.dfs(next, visited)\n",
    "        return visited\n",
    "\n",
    "    def bfs(self, node):\n",
    "        '''\n",
    "        广度优先遍历\n",
    "        :param node:\n",
    "        :return:\n",
    "        '''\n",
    "        seen = set([node])\n",
    "        queue = collections.deque([node])\n",
    "        while queue:\n",
    "            vertex = queue.popleft()\n",
    "            print(vertex)\n",
    "            for next in self.graph_dict[vertex]:\n",
    "                if next not in seen:\n",
    "                    seen.add(next)\n",
    "                    queue.append(next)\n",
    "\n",
    "\n",
    "graph_elements = {\"a\": {\"b\", \"c\"},\n",
    "                  \"b\": {\"a\", \"d\"},\n",
    "                  \"c\": {\"a\", \"d\"},\n",
    "                  \"d\": {\"e\", },\n",
    "                  \"e\": {\"d\", }\n",
    "                  }\n",
    "g = Graph(graph_elements)\n",
    "print(g.getVertices())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'a', 'b'}, {'a', 'c'}, {'b', 'd'}, {'d', 'c'}, {'e', 'd'}]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.findEdge()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2}\n",
      "(1, 2)\n",
      "{1, 2}\n"
     ]
    }
   ],
   "source": [
    "\n",
    "edge = set((1,2))\n",
    "print (edge)\n",
    "print(tuple(edge))\n",
    "print(edge)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(vertex1, vertex2) = tuple(edge)\n",
    "vertex1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 1, 'b': 2}\n",
      "{'a': {'c'}, 'b': 2}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'a': {'c', 'd'}, 'b': 2}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# if vertex1 in self.graph_dict:\n",
    "#     self.graph_dict[vertex1].add(vertex2)\n",
    "# else:\n",
    "#     self.graph_dict[vertex1] = {vertex2, }\n",
    "\n",
    "dict = {'a':1,'b':2}\n",
    "print(dict)\n",
    "dict['a'] = {'c',}\n",
    "print(dict)\n",
    "dict['a'].add('d')\n",
    "dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# **实验十一 图的最小生成树算法**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- # %%html -->\n",
    "<img src=\"实验十一.png\" width=\"70%\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "xpython",
   "language": "python",
   "name": "xpython"
  },
  "language_info": {
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "version": "3.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
